n_5 = 0
# 计算长度为01串的合法个数

inValid = [False] * 32


def isValid(num):
    cnt = 0
    if (num >> 1) & 1:
        cnt += 1
    if (num >> 2) & 1:
        cnt += 1
    if (num >> 3) & 1:
        cnt += 1
    if (num >> 4) & 1:
        cnt += 1
    if (num >> 0) & 1:
        cnt += 1
    if cnt <= 3:
        inValid[num] = True
        return True
    return False


dp = [[0] * 32 for _ in range(25)]  # 长度为i的串在后五位为mask 的情况下具有多少种可能性
for i in range(32):
    dp[5][i] = int(isValid(i))

for i in range(5, 24):  # 字符串长度
    for j in range(32):  # 32种状态
        prev_4 = (j & 15) << 1  # 获取后4位
        # 取0时一定成立
        dp[i + 1][prev_4] += dp[i][j]
        if inValid[prev_4 + 1]:
            dp[i + 1][prev_4 + 1] += dp[i][j]

print(sum(dp[24]))
